//Cracking coding interview 4.7
//Find common ancestor in binary tree (not necessary BST)
//9:50AM--10:23AM--10:47AM(bug free)--11:11AMrevised

#include<map>
#include<utility>

using namespace std;


struct Node {
	Node():l(NULL), r(NULL) {}
	Node *l, *r;

	int key;
};

struct Tree {
	Tree(Node *iroot): root(iroot) {}
	Node *root;
};

struct Param {
	Param () {
		lval=0;
		rval=0;
	}
	int Sum() {
		return lval+rval;
	}
	int lval;
	int rval;
};

Param Ancestor(Node *root, Node *a, Node *b, Node *&ancestor) {
	//should check a, b
	Param retVal;
	if(!root || ancestor) return retVal;
	
	if(root==a) {
		retVal.lval=1; 
	}
	if(root==b) {
		retVal.rval=1;
	}
	
	Param ret1, ret2;
	if (root->l) {
		ret1=Ancestor(root->l, a, b, ancestor); 
	} 
	if (root->r) {
		ret2=Ancestor(root->r, a, b, ancestor);
	}

	retVal.lval=(retVal.lval+ret1.lval+ret1.lval)>0;
	retVal.rval=(retVal.rval+ret1.rval+ret2.rval)>0;

	if(retVal.Sum()==2 && !ancestor) {
		ancestor=root;
	}

	return retVal;
}

int main(int argc, char *argv[]) {
	Node tree[4];
	tree[0].key=1;
	tree[1].key=3;
	tree[2].key=5;
	tree[3].key=8;

	tree[1].l=&tree[0];
	tree[1].r=&tree[2];
	tree[2].r=&tree[3];

	Node *p=NULL;
	Ancestor(&tree[1], &tree[0], &tree[2], p);

	return 0;
}